import java.util.ArrayDeque;
import java.util.Deque;
/**
 * 42. 接雨水
 * https://leetcode.cn/problems/trapping-rain-water/
 */
class TrappingRainWater {

    /**
     * 方法：trap
     * 逻辑: 使用动态规划的方法，分别计算每个位置左边和右边的最大高度，然后计算每个位置能存储的雨水量。
     * Args:
     * height: int[] - 表示每个位置的高度
     * Returns:
     * int - 能够存储的雨水总量
     * Time:
     * O(n) - 需要遍历数组三次
     * Space:
     * O(n) - 使用了两个额外的数组来存储左边和右边的最大高度
     */
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(height[i], leftMax[i - 1]);
        }
        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int j = n - 2; j >= 0; j--) {
            rightMax[j] = Math.max(height[j], rightMax[j + 1]);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }

    /**
     * 方法：trap1
     * 逻辑: 使用双指针的方法，分别从数组的两端向中间移动，计算每个位置能存储的雨水量。
     * Args:
     * height: int[] - 表示每个位置的高度
     * Returns:
     * int - 能够存储的雨水总量
     * Time:
     * O(n) - 只需要遍历数组一次
     * Space:
     * O(1) - 只使用了常数个额外空间
     */
    public int trap1(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0;
        int rightMax = 0;
        while (left < right) {
            leftMax = Math.max(height[left], leftMax);
            rightMax = Math.max(height[right], rightMax);
            ans += leftMax < rightMax ? leftMax - height[left++] : rightMax - height[right--];
        }
        return ans;
    }

    /**
     * 方法：trap3
     * 逻辑: 使用栈的方法，通过维护一个单调递减的栈来计算每个位置能存储的雨水量。
     * Args:
     * height: int[] - 表示每个位置的高度
     * Returns:
     * int - 能够存储的雨水总量
     * Time:
     * O(n) - 每个元素最多被压入和弹出栈一次
     * Space:
     * O(n) - 使用了一个栈来存储索引
     */
    public int trap3(int[] height) {
        Deque<Integer> st = new ArrayDeque<Integer>();
        int ans = 0;
        for (int i = 0; i < height.length; i++) {
            while (!st.isEmpty() && height[i] > height[st.peek()]) {
                int top = st.pop();
                if (st.isEmpty()) break;
                int left = st.peek();
                int distince = i - left - 1;
                int boundHeight = Math.min(height[i], height[left]) - height[top];
                ans += distince * boundHeight;
            }
            st.push(i);
        }
        return ans;
    }
}